#include <stdio.h>
#include "lib.h"

// void QUEUE
void init(Queue *q)
{
	q->dau=0;
	q->cuoi=-1;
}
void add(Queue *q,int x)
{
	q->cuoi++;
	q->hd[q->cuoi]=x;
}
int get(Queue *q)
{
	q->dau++;
	return q->hd[q->dau-1];
}


Schedule RR(ListProcess lp)
{
	Schedule sc;
	int i,j;
	int n=lp.N;
	//sao chep danh sach Pro vao mang trung gian
	Process p[100];
	for(i=0;i<n;i++)	
	{
		p[i]=lp.A[i];
	}
	//Tim pro dau tien de dua vao hang doi	
	int qmin=100;
	int smin=100;
	int pmin=0;
	for (i=0;i<n;i++)
	{
		if((p[i].Eqt<qmin)||(p[i].Eqt==qmin&&p[i].Est<smin))
		{
			qmin=p[i].Eqt;
			smin=p[i].Est;
			pmin=p[i].Pn;
		}	 	
	}
	printf("pmin1:%d \n",pmin);

	//Dua pro vao hang doi
	Queue q;
	init(&q);
	add(&q,pmin);	
	//Danh dau da them	
	int Added[100];
	//Khoi tao cho mang Added
	for(i=0;i<n;i++) Added[i]=0;
	Added[pmin-1]=1;
	// Tim kiem nhung pro co the dua vao
	int now=p[pmin-1].Eqt;
	printf("now1: %d \n",now);
	sc.Sn=0;
	while(q.dau<=q.cuoi)
	{		
		sc.Sa[sc.Sn]=get(&q);
		if(p[sc.Sa[sc.Sn]-1].St>0)
		{				
			sc.CPU[sc.Sn]=now;
			if(p[sc.Sa[sc.Sn]-1].St>=lp.Q)
			
				now=now+lp.Q;
			else now=now+p[sc.Sa[sc.Sn]-1].St;

			sc.Sn++;
			p[sc.Sa[sc.Sn-1]-1].St=p[sc.Sa[sc.Sn-1]-1].St-lp.Q;
		}
		printf("layra: %d \n",sc.Sa[sc.Sn-1]);
		printf("now= %d \n",now);
		//Tim kiem
		for (i=0;i<n;i++)
		{
			qmin=100;
			smin=100;
			pmin=0;
			for(j=0;j<n;j++)
			{
						
				if((Added[j]==0)&&(p[j].Eqt<=now)&&(p[j].St>0))
				{					
					if((p[j].Eqt<qmin)||(p[j].Eqt==qmin&&p[j].Est<smin))
					{
						qmin=p[j].Eqt;
						smin=p[j].Est;
						pmin=p[j].Pn;
					}
				}				
			}
			printf("pmin%d:%d \n",i,pmin);
			if(pmin!=0)
			{
				add(&q,pmin);	
				//Danh dau da them	
				Added[pmin-1]=1;			
			}			
			
		}			
		Added[sc.Sa[sc.Sn-1]-1]=0;
		printf("%d \n",p[sc.Sa[sc.Sn-1]-1].Pn);
		printf("%d \n",p[sc.Sa[sc.Sn-1]-1].St);
		if(p[sc.Sa[sc.Sn-1]-1].St>0)
		{
			add(&q,sc.Sa[sc.Sn-1]);
			Added[sc.Sa[sc.Sn-1]]=1;
		}
		
	}		
		
	for(i=0;i<n;i++)
	{
		j=sc.Sn-1;
		while(j>-1)
		{
			if(sc.Sa[j]==sc.Sa[j-1]) j--;
			if(sc.Sa[j]==i+1) 
			{
				sc.Wa[i]=sc.CPU[j]-p[i].Eqt;
				int k;
				for(k=j-1;k>=0;k--)
					if(sc.Sa[k]==i+1) sc.Wa[i]=sc.Wa[i]-(sc.CPU[k+1]-sc.CPU[k]);
				break;
			}
			j--;
		}
		

	}
	for(i=0;i<sc.Sn;i++) printf("%d ",sc.CPU[i]);	
	printf("\n");
	for(i=0;i<sc.Sn;i++) printf("%d ",sc.Sa[i]);
	printf("\n");		
	for(i=0;i<n;i++) printf("%d ",sc.Wa[i]);
	printf("\n");		
	sc.Wn=n;
	int sum=0;
	for(i=0;i<n;i++)
		sum=sum+sc.Wa[i];
	sc.Awt=(float) ((float) sum/ (float) n);
	printf("%f \n",sc.Awt);
	return sc;		
}
